package 回溯;

import java.util.ArrayList;
import java.util.List;

public class LeetCode22_括号生成 {
    private List<String> pathList = new ArrayList<>();
    private int maxPairCount = 0;

    public List<String> generateParenthesis(int n) {
        maxPairCount = n;
        backtracking("", 0, 0);
        return pathList;
    }

    private void backtracking(String path, int leftCount, int rightCount) {
        if(path.length() == maxPairCount * 2) {
            pathList.add(path);
            return;
        }
        if(leftCount < maxPairCount) {
            backtracking(path+"(", leftCount + 1, rightCount);
        }
        if(rightCount < leftCount) {
            backtracking(path+")", leftCount, rightCount+1);
        }
    }
}
